package com.tgy.programmer_code_interview_guide._02_linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 1/25/21 11:46 AM
 */
public class _09_复制带随机指针的链表_map {

    public static Node copyRandomList(Node head) {

        if (head == null) {

            return head;
        }

        Map<Node,Node> map = new HashMap<>();

        Node node = head;

        while (node != null) {

            Node randNode = node.random;
            if (randNode != null) {

                Node newRandNode = map.get(randNode);
                if (newRandNode == null) {

                    newRandNode = new Node(randNode.val);
                    map.put(randNode,newRandNode);
                }

            }
            node = node.next;
        }

        Node dummyNode = new Node();
        Node tailNode = dummyNode;

        node = head;
        while (node != null) {

            Node newNode = map.get(node);

            if (newNode == null) {

                newNode = new Node(node.val);
            }

            tailNode.next = newNode;
            tailNode = newNode;

            if (node.random != null) {

                newNode.random = map.get(node.random);
            }

            node = node.next;
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {

        Node root = new Node(7);

        Node node01 = new Node(13);
        root.next = node01;
        node01.random = root;

        Node node02 = new Node(11);
        node01.next = node02;

        Node node03 = new Node(10);
        node02.next = node03;
        node03.random = node02;

        Node node04 = new Node(1);
        node03.next = node04;

        node02.random = node04;
        node04.random = root;

        Node node = root;

        while (node != null) {

            System.out.println(node);
            node = node.next;
        }

        Node copyRoot = copyRandomList(root);

        System.out.println("======");
        node = copyRoot;
        while (node != null) {

            System.out.println(node);
            node = node.next;
        }

//        System.out.println(copyRoot);
    }
}
